package com.learn.tree;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;

/**
 * 统计二叉树最大层的节点个数
 */
public class MaxTreeLength {
    public static class Node {
        private Node left;
        private Node right;
        private int value;

        public Node(int value) {
            this.value = value;
        }
    }

    public int findMaxLength(Node head) {
        if (head == null) {
            return 0;
        }
        Queue<Node> queue = new LinkedList<>();
        int max = 0;
        //当前所在的层次
        int curLevel = 1;
        //当前层的节点个数
        int curLevelNodes = 0;
        //记录节点所在的层
        Map<Node, Integer> levelMap = new HashMap<>();
        levelMap.put(head, curLevel);
        queue.add(head);
        while (!queue.isEmpty()) {
            Node node = queue.poll();
            int level = levelMap.get(node);
            if (node.left != null) {
                queue.add(node.left);
                levelMap.put(node.left, level + 1);
            }
            if (node.right != null) {
                queue.add(node.right);
                levelMap.put(node.right, level + 1);
            }

            if (curLevel == level) {
                //弹出的节点还在当前层，则节点树+1
                curLevelNodes++;
            } else {
                curLevel++;
                max = Math.max(curLevelNodes, max);
                curLevelNodes = 1;
            }
        }
        return Math.max(curLevelNodes, max);
    }
}
